package com.leetcode.partition14;

import java.io.*;
import java.util.*;

/**
 * @author `RKC`
 * @date 2022/1/21 18:56
 */
public class LC1345跳跃游戏IV_bfs {

    private static final int N = (int) (5e4 + 10), INF = 0x3f3f3f3f;
    private static Map<Integer, List<Integer>> map = new HashMap<>();
    private static Queue<Integer> queue = new ArrayDeque<>(N);
    private static int[] dist = new int[N];

    private static int n = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        int[] arr = new int[s.length];
        for (int i = 0; i < s.length; i++) arr[i] = Integer.parseInt(s[i]);
        writer.write(minJumps(arr) + "\n");
        writer.flush();
    }

    public static int minJumps(int[] arr) {
        n = arr.length;
        //类似于建图，每个节点的一对多的关系
        for (int i = n - 1; i >= 0; i--) {
            List<Integer> indices = map.getOrDefault(arr[i], new ArrayList<>());
            indices.add(i);
            map.put(arr[i], indices);
        }
        return bfs(arr);
    }

    private static int bfs(int[] arr) {
        Arrays.fill(dist, INF);
        queue.add(0);
        dist[0] = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll(), w = dist[u];
            if (u == n - 1) return w;
            //在遍历的过程中加入前后两个节点
            if (u + 1 < n && dist[u + 1] == INF) {
                dist[u + 1] = w + 1;
                queue.add(u + 1);
            }
            if (u - 1 >= 0 && dist[u - 1] == INF) {
                dist[u - 1] = w + 1;
                queue.add(u - 1);
            }
            //遍历邻节点
            List<Integer> next = map.getOrDefault(arr[u], null);
            if (next == null) continue;
            for (int v : next) {
                if (dist[v] == INF) {
                    queue.add(v);
                    dist[v] = w + 1;
                }
            }
            //已经更新了u节点能够更新的点，bfs再次poll出这个u也不会发生更新，所以从队列中移出避免多余的遍历
            map.remove(arr[u]);
        }
        return -1;
    }
}
